1. Field of the Invention
This invention relates to a residue calculation circuit suitable for use, for example, with a rate conversion apparatus for converting a PAL signal of the D-1 format into another PAL signal of the D-2 format.
2. Description of the Related Art
A residue number system (RNS) is first described prior to description of conventional residue calculation circuits. The residue number system represents, in order to represent a numerical value, a set of residue numbers which do not have a common measure and accordingly are prime relative to each other, and since it treats numerical values as integral numbers, it allows addition, subtraction and multiplication but does not allow division.
A residue number system when the residue numbers are 3, 5 and 7 is described. Since 3.times.5.times.7=105 (dynamic range), any one of the numerical values from 0 to 104 at the greatest can be represented by a combination of the residue numbers.
Since 6=0+3.times.2=1+5.times.1=6+7.times.0, the numerical value 6 is represented as (0, 1, 6) with regard to the residue numbers 3, 5 and 7.
Subsequently, addition, subtraction and multiplication between 4 and 6 will be described.
First, addition will be described. Since 4=(1, 4, 4) and 6=(0, 1, 6), EQU (1, 4, 4)+(0, 1, 6)=(1, 0, 3) (1)
The equation (1) stands since 1+0=1+3.times.0, 4+1=0+5.times.1, and 4+6=3+7.times.1. Further, since
10=1+3.times.3=0+5.times.2=3+7.times.1 (1, 0, 3) represents 10, and the equation (1) above represents that 4+6=10.
Subsequently, subtraction will be described. EQU (1, 4, 4)-(0, 1, 6)=(1, 3, 5) (2)
The equation (2) stands since 1-0=1+3.times.0, 4-1=3+5.times.0, and 4-6=5-7.times.1. Further, since
-2=1-3.times.1=3-5.times.1=5-7.times.1 (1, 3, 5) represents -2, and the equation (2) above represents that 4-6=-2. Further, since
103=1+3.times.34=3+5.times.20=5+7.times.14 -2=103. Further, 0=105 and -1=104. This can apparently be seen from FIG. 2. In particular, while the numerical value increases in the clockwise direction like 1, 2, 3, . . . , it decreases in the counterclockwise direction like -1, -2, -3, . . . . Whether the clockwise direction is used or the counterclockwise direction is used depends upon setting by a designer.
Subsequently, multiplication will be described. EQU (1, 4, 4).times.(0, 1, 6)=(0, 4, 3) (3)
The equation (3) stands since 1.times.0=0+3.times.0, 4.times.1=4+5.times.1, and 4.times.6=3+7.times.3. Further, since
24=0+3.times.8=4+5.times.4=3+7.times.3 (0, 4, 3) represents 24, and the equation (3) above represents that 4.times.6=24.
It is to be noted that, in order to return the notation of a numerical value from the residue number notation to the binary notation, a method called Chinese remainder theorem has been used for a long time and is used at present.
With the residue number system, since actual calculation is performed for each residue number, a numerical value for a subject of calculation remains within a comparatively small range in value, and accordingly, there is an advantage in that the restriction in operation speed of an electronic circuit necessary for calculation of a comparatively large value can be moderated significantly.
While the residue number system has the advantage just described, conventional residue calculation circuits employ a method which makes use of a lookup table provided in a ROM in order to calculate residues with respect to specific residue numbers (3, 5 and 7 in the example described above) as a result of calculation. An exemplary one of conventional residue calculation circuits will be described below with reference to FIGS. 3 to 5.
Referring first to FIG. 3, there is shown a rate conversion apparatus for converting a PAL signal of the D-1 format into another PAL signal of the D-2 format. A PAL signal D-1PAL of the D-1 format inputted to a D-1 encoder 1 is separated into a brightness signal Y of the sampling frequency of 13.5 MHz and a pair of color difference signals B-Y and R-Y of the sampling frequency of 6.75 MHz. The brightness signal Y is inputted to a rate conversion circuit 2 while the color difference signals B-Y and R-Y are inputted to a matrix circuit 3. The brightness signal Y is converted into another brightness signal Y' of the sampling frequency of 17.73 MHz by the rate conversion circuit 2. The color difference signals B-Y and R-Y are axially converted into color signals u and v, respectively, by the matrix circuit 3. The color signals u and v are converted into color signals u' and v' of the sampling frequency of 8.87 MHz by a pair of rate conversion circuits 4 and 5, respectively, and then modulated with a subcarrier of 4.43 MHz into a chroma signal CR by a chroma modulation circuit 6. The chroma signal CR and the brightness signal Y' are added by an addition circuit 7 and outputted from the addition circuit 7 as a PAL signal D-2PAL of the D-2 format.
FIG. 4 shows details of the rate conversion circuits 2, 4 and 5 of FIG. 3. Referring to FIG. 4, a signal a (brightness signal Y or color signal u or v) inputted to the rate conversion circuit 2, 4 or 5 shown is separated into residues x, y and z with regard to specific residue numbers, for example, 3, 5 and 7, and the residues x, y and z are inputted to rate converters 9a, 9b and 9c, respectively. Residues x', y' and z' with regard to 3, 5 and 7 after the rate conversion are composed by a decoder 10 and outputted from the decoder 10 as a signal b (brightness signal Y' or color signal u' OF v').
FIG. 5 shows details of the rate converters 9a, 9b and 9c which include a FIR filter as a conventional residue calculation circuit. A portion of the FIR filter except a FIFO (first-in first-out) circuit 21 makes a conventional FIR filter. Referring to FIG. 5, the FIR filter shown includes, in addition to the FIFO circuit 21, three delay circuits 11 to 13 which may be D-type flip-flops. The delay time .tau. of the delay circuits 11 to 13 is set to 1/13.5 MHz for the rate conversion circuit 2 and to 1/6.75 MHz for the rate conversion circuits 4 and 5.
The FIR filter further includes four multipliers 14 to 17, which provide outputs An (n=0 to 3) given by EQU An=(Kn.times.Sn) mod R (4)
where (Kn.times.Sn) mod R represents a residue of a result of the multiplication of (Kn.times.Sn) with regard to the residue number R. For example, when R=31 and (Kn.times.Sn)=15, An=15, and if (Kn.times.Sn)=40, then An=40-31=9. The multipliers 14 to 17 may be lookup tables provided by a ROM.
The FIR filter further includes three adders 18 to 20, which may be lookup tables provided by a ROM, similarly to the multipliers 14 to 17.
Output values of the adders 18 to 20 when the residue number R=31, A0=5, A1=25, A2=3 and A3=10 will be described subsequently with reference to FIG. 5. First, the adder 18 calculates A0+A1=30 and outputs the residue 30 (=30+0.times.31) with regard to the residue number R as a numerical value B1. Then, the adder 19 calculates B1+A2=33 and outputs the residue 2 (33=2+1.times.31) with regard to the residue number R as a numerical value B2. Finally, the adder 20 calculates B2+A3=12 and outputs the residue 12 with regard to the residue number R as a numerical value B3. The FIFO circuit 21 converts, when the rate conversion circuit is for the brightness signal Y, the residue B3 of the sampling frequency of 13.5 MHz into another residue Sout of the sampling frequency of 17.73 MHz by rate conversion, but converts, when the rate conversion circuit is for the color signal u or v, the residue B3 of the sampling frequency of 6.75 MHz into another residue Sout of the sampling frequency of 8.87 MHz by rate conversion.
In the FIR filter described above, however, since not only the multipliers 14 to 17 but also the adders 18 to 20 are constituted from a ROM, increase of the calculation speed and reduction of the scale of the FIR filter when it is integrated into an integrated circuit cannot be achieved.